1. Field of the Invention
This invention relates to the field of digital data processing systems, and more particularly relates to communication of information between components in such systems.
2. Background Information
In the field of digital data processing systems, as the computer capabilities of data processing devices have increased, both in terms of speed, efficiency, and complexity, the number of users or applications which may be concurrently supported by a single central processing device has also increased.
Often, the number of remote devices in a system exceeds the number of separate input/output (I/O) ports of the central processing device. In this case, a multiplexing communications system may be implemented which allows multiple remote devices to share a common one of the central device's I/O ports.
Remote or "peripheral" devices, such as user terminals, printers, modems, data storage devices, data acquisition devices, and the like, must frequently exchange information with a central processing unit, and as the number of remote devices increases, such communication of data between peripheral devices and a central unit must be highly efficient. The communications system must also allow the central device to selectively exchange data with any one of the remote devices, and each remote device must have a unique identity as seen by the central device. Accordingly, any communications scheme for multiplexed systems must include not only the hardware components for implementing the actual data link, but also a communications protocol for use with the hardware, for allowing data transferred on the link to be associated with a particular sender or receiver.
Maintaining the identity of devices and data in a multiplexed system can be accomplished in a number of ways. One method involves the assignment of a unique identification code to each device in the system, including identification of the sender and/or receiver of data within the data itself as it is transmitted along the shared data link. An example of this is the so-called address/packet protocol, wherein all information transmitted on the shared data link is of a standard format which includes device identification fields. Packets of data transmitted on a data link that is shared by multiple devices could be received by all devices at once; each device could then decode the identification field of the incoming packets to determine whether the data is intended for it.
In another type of multiplexing, called Time Division Multiplexing (TDM), the identity of data is determined by the time of its transmission on the shared medium. Each device sharing a common data link is allocated, in a regular and cyclical fashion, a fixed period of time during which it has access to the data link. If a first device needs to send data, it must wait until its allocated time slot before sending it. The identity of the sending device is thus implicitly known to the receiving device according to the time of transmission.
Alternately, access to a shared data link can be multiplexed on a demand, or First-Come-First-Served (FCFS) basis, in which a device is granted access to the data link not in a cyclical fashion, but according to its needs. Often, demand multiplexing is implemented through the use of a separate multiplexor unit, which receives requests for access to the shared data link from multiple devices, and allocates access according to a FCFS algorithm. With demand multiplexing, the multiplexor logic must be capable of informing each device of the source of data transmitted on the shared link, since time slices are not allocated in a repeating, cyclical manner.
Additionally, variations of demand multiplexing can be implemented wherein the FCFS algorithm is replaced by a weighted algorithm which considers other factors, such as varying levels of device priority, in allocating access to the multiplexed data link. In any non-symmetrical implementation in which one device may have temporary or permanent priority over another, care must be taken that low priority devices are not prevented entirely from gaining access to the shared data link by higher priority devices. Typically it is the duty of the multiplexing logic (either software or hardware) to ensure equity or near-equity of access to a shared communication medium.
The aforementioned methods of multiplexing each have their disadvantages. Multiplexing schemes typically require substantial hardware support for allocating access to the shared link in an efficient and equitable manner. In pure TDM schemes, inefficiency is unavoidably introduced if any devices are idle, because the shared link would go unused during an idle device's time slot. Though no bandwidth may be lost in demand and other priority-based access schemes, these methods may also suffer from inefficiency if the multiplexing algorithm allowed one very active device to dominate over all others. In address/packet protocol multiplexing, on the other hand, each participating device must provide hardware or software for "de-packetizing" all incoming data packets to determine the intended recipient. Hardware or software must also be provided in each device for "packetizing" all outgoing data. The processing overhead for packetization and depacketization is further increased if the packet size is allowed to be variable under a given protocol.
The addition of devices or user terminals to multi-user systems often requires a great deal of system reconfiguration. As the limits of the system's communications hardware are reached, new hardware must be added, or the existing hardware must be replaced by new, more densely packed hardware. Such hardware changes typically involve reconfiguration of the system software or firmware to accommodate the new hardware.